package com.jhy.review.day08;

/**
 * 2022年9月1日10:53:00
 * 求一个数的小和问题
 * 1、先讲什么是小和
 * 当前的数的左边有几个数比它小，然后把这些数相加起来。 可以暴力求解 是n平方
 * 例如  1 3 4 2 5 的小和是 16 0+1+1+3+1+1+3+4+2=16
 * 2、上面求小和的过程 也可以等价于 一个数组当中的右边有几个数比本身大。有几个数乘以本身相加起来。（左侧小的才产生小和）
 * 用归并排序求
 * 13425
 * 134   25
 * 13 4  2 5  左边指向1 右边指向4 先产生一个1数比1大为4 1*1=1 然后左边指向3 右边还是指向4 产生一个数比3大 3*1=3
 * 1 3 这里的1 右侧当中有几个数比当前数大  是3所以1个数 1*1  完成 13合并
 */
public class smallSum {
    public static int smallSum(int[] arr){
        if(arr==null || arr.length<2){
            return 0;
        }
        return  MergeSort(arr,0,arr.length-1);
    }
    public static  int MergeSort(int[] arr,int l,int r){
        if(l == r){
            return 0;
        }
        int mid =l + ((r-l)>>1);
        return MergeSort(arr,l,mid) + MergeSort(arr,mid+1,r) +
                merge(arr,l,mid,r);
    }
//    传入mid是为了记录下标位置
    public static int merge(int[] arr, int l, int m, int r) {
//        构造一个辅助的空间
        int[] help = new int[r-l+1];
        int p1 = l;
        int p2 = m+1;
//        一个记录help数组的下标的空间
        int i = 0;
//        记录我们放回的结果
        int res = 0;
        while(p1 <= m && p2 <= r){
            res += arr[p1]<arr[p2] ? (r-p2+1)*arr[p1]:0;
            // 这里不能和归并排序条件一样了 归并那边是可以 <= 的
            help[i++] = arr[p1] < arr[p2] ? arr[p1++]:arr[p2++];
        }
        while(p1<=m){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }
//        赋值操作
        for (int j = 0; j < help.length; j++) {
            arr[l+j] = help[j];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,4,2,5};
        int sum = smallSum(arr);
        System.out.println(sum);
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        System.out.println();
    }

}
